This study employs a Phase I, double-blind, randomized, dose-escalation, placebo-controlled study design, with serious dose-limiting toxicity as the primary endpoint. Medically stable, HIV-infected subjects with less than 50 CD4+ T cells and no evidence of serious ongoing opportunistic infections will be enrolled in Part A. Three sequential groups of 12 subjects each will be randomly assigned in a 3:1 manner to receive twice-weekly, subcutaneous injections of either rhIL-12 or matching placebo for four weeks, as an adjunct to their stable antiretroviral therapy. Subjects must maintain stable antiretroviral therapy, as well as initiate and maintaint PCP prophylaxis throughout this course of study. Once the MTD of rhIL-12 is determined from Part A, a cohort of 18 subjects with CD4+ T cell counts of 300-500 cells will be enrolled to receive twice-weekly, subcutaneous injections of either the MTD of rhIL-12 or matching placebo for four weeks. No dose escalation for part B.